/**
 * 组合总和
 *
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 *
 * 示例 1：
 * 输入：candidates = [2,3,6,7], target = 7
 * 输出：[[2,2,3],[7]]
 * 解释：
 * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 * 7 也是一个候选， 7 = 7 。
 * 仅有这两种组合。
 *
 * 示例 2：
 * 输入: candidates = [2,3,5], target = 8
 * 输出: [[2,2,2,2],[2,3,3],[3,5]]
 *
 * 示例 3：
 * 输入: candidates = [2], target = 1
 * 输出: []
 *
 * 提示：
 * 1 <= candidates.length <= 30
 * 2 <= candidates[i] <= 40
 * candidates 的所有元素 互不相同
 * 1 <= target <= 40
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1.这里我们将每一中可能性排列在草稿纸上我们会发现, 这好像全排列, 我们只需要将所有的可能性都排列出来,
 * 再筛选其中的可行方案, 最后回溯回去再找可行方案就可以了
 * 时间复杂度 : O(n * 2^n)
 * 空间复杂度 : O(n)
 *
 * 2. 这里我们用剪枝优化, 并且在 prev 的使用方法上也进行了优化, 我们采用传之前的下标的方式来进行深搜
 *  时间复杂度 : O(k * m)
 *  空间复杂度 : O(n)
 */

public class Main {


    // 这里我们将所有的变量设置为全局的, 这样我们后面再用到这列参数的时候直接用就可以了
    // 不用再将这些参数设置到深搜函数头中
    // 返回 lists
    List<List<Integer>> lists;

    // 深搜中记录每一组的 list
    List<Integer> list;

    // 原来的可用数组
    int[] nums;

    // 数组长度
    int n;

    // 要达到的目标值
    int tmp;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        // 在函数中初始化
        lists = new ArrayList<>();
        list = new ArrayList<>();
        nums = candidates;
        n = nums.length;
        tmp = target;


        // 这里要是用的下标法, 我们要确保数组有序, 所以在深搜前先将数组进行排序
        Arrays.sort(nums);

        // 从 sum 为 0 和下标为 0 开始深搜
        dfs(0, 0);

        // 返回 lists
        return lists;
    }

    // 这个是没有用剪枝的回溯

    // 这里的 sum 使用来记录上层 dfs 的结果的
    // prev 使用来记录上面 + 上的数是多少
    private void dfs1 (int sum, int prev) {

        if (sum == tmp) {
            lists.add(new ArrayList<>(list));
            return;
        }

        if (sum > tmp) {
            return;
        }

        for (int i = 0; i < n; i++) {

            // 这里不仅要判断 sum 嗨呀判断 nums[i] 和前面一个数的大小
            if (nums[i] >= prev && sum < tmp) {
                list.add(nums[i]);
                sum += nums[i];
                prev = nums[i];
            } else {
                continue;
            }

            dfs1 (sum, prev);

            // 恢复现场
            // 这里的恢复现场会比较麻烦, 因为需要知道 前一个 + 的 prev,
            // 但还好的是我们的 list 中存了这个数, 所以我们直接返回 list
            // 的最后一个数字就可以了(要是 list 中有数字的话, 没数字直接更新成 0 就可以了)
            list.remove(list.size() - 1);
            sum -= nums[i];
            prev = list.size() > 0 ? list.get(list.size() - 1) : 0;
        }
    }


    // ********************************************************
    // 2. 用了剪枝的深搜
    // 这里的 start 是指上次 + 的下标
    private void dfs (int sum, int start) {

        // 这里要是相等了就是有效的 list, 将他加入 lists 中
        if (sum == tmp) {
            // 这里要 new , 拷贝一下, 避免我们后续在修改 list 的时候 lists 中的也跟着变
            lists.add(new ArrayList<>(list));

            // 不要忘记结束哦
            return;
        }

        // 从 start 下标开始 加
        for (int i = start; i < n; i++) {
            int current = nums[i];

            // 剪枝, 这里因为是有序数组, +前面的就已经大于目标和了
            // 所以这条循环直接结束就可以了
            // 正因如此, 在外面也不用判断 sum > tmp 了
            if (sum + current > tmp) {
                break;
            }

            // 这里是有效的数字, 加入 list
            list.add(nums[i]);

            // 深搜, 这里因为前面的数字可能还是可以相加的, 所以我们传这一次的 i
            // sum 就可以直接传 sum + current 了, 这样后续恢复现场的时候就不用恢复 sum
            dfs (sum + current, i);

            // 恢复现场
            list.remove(list.size() - 1);
        }
    }

    public static void main(String[] args) {
        Main test = new Main();
        test.combinationSum(new int[]{2, 3, 6 , 7}, 7);
    }
}